package F.树;

import java.util.LinkedList;
import java.util.Queue;

public class _104_二叉树的最大深度 {

    /**
     * 自解：利用后序遍历来获得深度====不会了
     * 递归终止条件 节点为根节点时 输出最大深度
     * @param root
     * @return
     */
    int maxdepth =0;
    int max =0;

    public int maxDepth(TreeNode root) {

        if (root == null){
            if (maxdepth> max){
                max = maxdepth;

            }
            maxdepth--;
            return max;
        }
        maxdepth++;
        maxDepth(root.left);
        //maxdepth--;
        maxDepth(root.right);


        return max;
    }

    /**
     * 题解：递归方法左子树和右子树的最大深度 ll 和 rr，那么该二叉树的最大深度即为 max（l，r）+1
     * 递归函数的作用计算传入树的最大深度
     *  终止条件根为0
     * @param root
     * @return
     */
    public int maxDepth1(TreeNode root) {
        if (root == null){
            return 0;
        }else {
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);

            return Math.max(left,right)+1;
        }
    }

    /**
     * 题解：广度优先搜索--耗时太大
     * 弄一个队列 所有层的进去
     * 先放入根节 只要queue不为空 就一直操作
     * 用queue的size来决定需要循环弹出几次 然后循环弹出内 加入其左右孩子
     * @param root
     * @return
     */
    public int maxDepth2(TreeNode root) {

        if (root == null){
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int ans=0;
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size>0){
                TreeNode node = queue.poll();
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
                size--;

            }
            ans++;
        }

        return ans;

    }

}
